class Solution(object):
    def minimumCost(self, sentence, k):
        sentence = sentence.split(' ')
        n = len(sentence)
        index = n - 1
        now = 0
        while index >= 0 and now + len(sentence[index]) + 1 <= k + 1:
            now += len(sentence[index]) + 1
            index -= 1
        if index == -1:
            return 0
        DP = [0] * n
        for i in range(n):
            now_length = len(sentence[i]) + 1
            if i == 0:
                min_val = (k + 1 - now_length) ** 2
            else:
                min_val = DP[i - 1] + (k + 1 - now_length) ** 2
                for j in range(i - 1, -1, -1):
                    now_length += len(sentence[j]) + 1
                    if now_length  <= k + 1:
                        if j == 0:
                            min_val = min(min_val, (k + 1 - now_length) ** 2)
                        else:
                            min_val = min(min_val, DP[j - 1] + (k + 1 - now_length) ** 2)
                    else:
                        break
            DP[i] = min_val
        return min(DP[index:])


data = Solution()
sentence = "i love leetcode"
k = 12
print(data.minimumCost(sentence, k))